競技プログラミングでバグった時のためのチェックリスト： DFS ・ BFS
from 競技プログラミングでバグった時のためのチェックリスト
競技プログラミングでバグった時のためのチェックリスト：DFS・BFS
訪問したことを記述するタイミングは適切か？
ABC350D - New Friends
FIXED: visitedの書き込みタイミングに誤りがあった。
whileループで取り出した後の頂点の後にvisitedをつける場合、
stackの中に入っているがまだ未訪問の頂点に複数回アクセスできてしまう。
code:diff
stack.push_back(i);
+ visitedi = true;
connected_count.push_back(0ll);
while (not stack.empty()) {
const size_t current = stack.back();
stack.pop_back();
- visitednext = true;
connected_count.back()++;
for (const auto& next:adj_listcurrent) {
if (not visitednext) {
// FIXED: visitedの書き込みタイミングに誤りがあった。
// whileループで取り出した後の頂点の後にvisitedをつける場合、
// stackの中に入っているがまだ未訪問の頂点に複数回アクセスできてしまう。
+ visitednext = true;
stack.push_back(next);
}
}
}